1. Field of the Invention
This invention relates to telecommunications, and more particularly to a method and apparatus for signal mapping and shaping using an improved shell mapping algorithm.
2. Description of Related Art
In many communication systems, digital bits must be transformed into analog signals for transmission, and the analog signals transformed back into digital bits upon receipt. Generally, a modulator/demodulator (modem) is used to perform these functions. To accommodate the problem of data loss due to noise and other causes, the need for high bit rates, and the need for reliable connections under low power conditions, a variety of error correction codes and modulation schemes have been proposed, and in many instances, adopted by industry.
Typically, data input to a modem is expressed in a binary form. Data is transmitted at a bit rate (e.g., B bits per second), where the bit rate is defined as the number of bits to be transmitted and received, including the actual binary information data and a predetermined number of redundancy bits needed by coding in a selected system. During transmission, the binary data is typically transmitted and received in a form of a series of symbols at a symbol rate of S symbols per second. Thus, each symbol contains B/S bits of binary data.
Each symbol can be represented by one of the possible line signal states generated by the modem. Various modulation techniques may be used to convert data into line signal states. For example, in quadrature amplitude modulation (QAM), the line signal states can be represented by a set of complex numbers, namely by a set of points in a two-dimensional signal constellation. For example, for a bit rate B and a symbol rate S, where B/S is an integer D, a signal constellation of size 2.sup.D is needed to represent D bits in each symbol. Thus, if B=12000 bits/second and the symbol rate S is 2400 symbols/second, D=5 bits/symbol, and a 32-point two-dimensional signal constellation is used, providing a scheme for mapping one out of 32 possible complex signal points according to 5 input data bits.
However, for high speed modems, multiple symbol rates and bit rates may be used to facilitate more efficient use of the available channel bandwidth. In such instances, the ratio B/S may not be always an integer; that is, the data rate is not always a multiple of the symbol rate. To accommodate this, a scheme that maps an integer number of bits to several symbols is needed. Several ways of doing this have been defined, including switched constellations, modulo mapping, and shell mapping.
Shell mapping has been adopted for the ITU-T V34 modem standard. In shell mapping, a two-dimensional signal constellation is partitioned into M equal size "shells" each of which contains R signal points. R is typically chosen to be 2.sup..nu., where .nu. is an integer greater than or equal to zero. For Q input data bits, K=Q-(N*.nu.) bits, are used for shell mapping, generating N shell indices or selectors m.sub.i (i=1, 2, . . . N) ranging from 0 to M-1. For each symbol, one of these shell indices is used to choose a corresponding one of the M shells in the signal constellation, and .nu. bits are used to choose one of the 2.sup..nu. points within that shell. If a convolutional encoder is employed, among .nu. bits, c bits are coding bits which are the output of the convolutional encoder, and are used to select one of the 2.sup.c subsets. The remaining u=.nu.-c bits are used to select one of the 2.sup.u points in the chosen subset in the chosen shell. When no convolutional encoder is employed, c=0 and u=.nu.. The constellation size is L=M*2.sup.u+c. The signal constellation may be partitioned into subsets according to Ungerboeck set partitioning principles, as is known in the art.
In order to select the N-tuple [m.sub.1, m.sub.2, . . . m.sub.N ] using K bits, first a "cost" is assigned to each shell. Since a main purpose of an efficient mapping scheme is to achieve a low average signal power, the average signal power within a shell is assigned as its "cost". However, for computational convenience, the "cost" is set to the shell index. Thus, the innermost shell has cost 0, the next shell has cost 1, and so on. This approximation is quite workable, in particular as the constellation becomes larger. Since costs are additive, the total costs of N symbols is m.sub.1 +m.sub.2 . . . +m.sub.N. Note that there are M.sup.N combinations of N shell indices, but only 2.sup.K .ltoreq.M.sup.N input K-bit combinations. Thus, certain combinations of shells will be excluded. In conventional systems, an efficient shell mapping scheme minimizes the cost by selecting the 2.sup.K combinations that have the least total cost. If the input K bits is expressed as a number X, a conventional shell mapping algorithm ensures that as X increases, the corresponding total cost is non-decreasing.
In most implementations of shell mapping, particular shells are selected on a frame-by-frame basis by an algorithm that can be implemented efficiently on a fixed-point digital signal processor (DSP) using look-up tables. In this method, signal shaping and mapping are integrated in a seamless fashion. Further details of conventional shell mapping are set forth in Signal mapping and shaping for V.fast, Motorola Information Systems contribution D196, CCITT Study Group XVIII, Geneva, June 1992, and U.S. Pat. No. 5,428,641 to Long, assigned to Motorola, Inc., which is hereby incorporated by reference.
Since the V.34 modem standard was finalized, there has been much interest in seamless data rate changing. It has been suggested that seamless rate changing can be used as a fast rate changing method on rapidly varying channels or as a rate negotiation method that minimizes short term affects on throughput. Both of these goals are achievable and several methods to implement such functionality have already been proposed within standards committees.
All of the schemes proposed to date need to know the number of bits to be mapped before they can be implemented. This becomes a burdensome restriction when rapid rate changing is needed. In the V.34 modem standard, a shell mapping algorithm that maps an integer number of bits to 8 symbols is used. The number of bits is determined based on the desired data rate and symbol rate, and tables are then calculated to efficiently implement the algorithm. When changing data rate, new tables are calculated while still using the old tables. A problem has been that, after negotiation of a new rate, a certain amount of time must be allowed for new shell mapping tables to be generated. This approach also takes extra memory, since multiple tables must exist concurrently.
It would be desirable to have a method of changing data rates that avoids these problems. The present invention provides such a method.